package sort;

import java.util.Arrays;

public class MergeSort {

    public static void mergesort(int[] array, int start, int end) {
        if (start < end) {
            //折半成两个小集合
            int mid = (start + end) / 2;
            mergesort(array,start,mid);
            mergesort(array, mid + 1, end);
            //把两个小集合归并成一个大集合
            merge(array,start,mid,end);
        }
    }

    public static void merge(int[] array, int start, int mid, int end) {
        //额外开辟大集合
        int[] tempArray = new int[end - start + 1];
        int p1 = start;
        int p2 = mid + 1;
        int p = 0;
        while ((p1 <= mid) && (p2 <= end)) {
            if (array[p1] < array[p2]) {
                tempArray[p++] = array[p1++];
            } else {
                tempArray[p++] = array[p2++];
            }
        }
        //左边小集合还有剩余
        while(p1 <= mid) {
            tempArray[p++] = array[p1++];
        }
        //右边小集合有剩余
        while (p2 <= end) {
            tempArray[p++] = array[p2++];
        }
        //把大集合的元素复制回原数组
        for (int i = 0; i < tempArray.length; i++) {
            array[i + start] = tempArray[i];
        }
    }

    public static void main(String[] args) {
        int[] array = {5,3,8,2,1,7,10};
        mergesort(array,0, array.length - 1);
        System.out.print(Arrays.toString(array));
    }

}
